{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rearrange String k Distance Apart"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string #counting #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串 #计数 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rearrangeString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 距离间隔重排字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非空的字符串&nbsp;<code>s</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，你要将这个字符串&nbsp;<code>s</code>&nbsp;中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离 <strong>至少</strong> 为&nbsp;<code>k</code>&nbsp;。如果无法做到，请返回一个空字符串&nbsp;<code>\"\"</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"aabbcc\", k = 3\n",
    "<strong>输出: </strong>\"abcabc\" \n",
    "<strong>解释: </strong>相同的字母在新的字符串中间隔至少 3 个单位距离。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"aaabc\", k = 3\n",
    "<strong>输出: </strong>\"\" \n",
    "<strong>解释:</strong> 没有办法找到可能的重排结果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"aaadbbcc\", k = 2\n",
    "<strong>输出: </strong>\"abacabcd\"\n",
    "<strong>解释:</strong> 相同的字母在新的字符串中间隔至少 2 个单位距离。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 3 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;仅由小写英文字母组成</li>\n",
    "\t<li><code>0 &lt;= k &lt;= s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rearrange-string-k-distance-apart](https://leetcode.cn/problems/rearrange-string-k-distance-apart/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rearrange-string-k-distance-apart](https://leetcode.cn/problems/rearrange-string-k-distance-apart/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabbcc\"\\n3', '\"aaabc\"\\n3', '\"aaadbbcc\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        \n",
    "        chr_freq = collections.Counter(s)\n",
    "        \n",
    "        maxHeap = [(-1 * freq, chr) for chr, freq in chr_freq.items()]\n",
    "        heapq.heapify(maxHeap)\n",
    "        \n",
    "        Q = collections.deque()\n",
    "        res = \"\"\n",
    "        while maxHeap:\n",
    "            freq, c = heapq.heappop(maxHeap)    #要想实现，必须先弹出最大次数的那个\n",
    "            freq *= -1\n",
    "\n",
    "            res += c\n",
    "            Q.append((freq - 1, c))\n",
    "\n",
    "            if len(Q) == k:             #能够构成一个长度为k的窗口。则后移\n",
    "                f, c = Q.popleft()\n",
    "                if f > 0:\n",
    "                    heapq.heappush(maxHeap, (-1 * f, c)) ### \n",
    "        \n",
    "        return res if len(res) == len(s) else \"\"\n",
    "\n",
    "### 下一步你具体选什么是皆有可能的，但是维系这个合法模式不会变化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class heap_item:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "    def __repr__(self):\n",
    "        return f\"(letter = {self.key}, count = {self.value})\"\n",
    "    def __lt__(self, other):\n",
    "        return self.value > other.value\n",
    "def put_chosen(dest, chosen):\n",
    "    while len(chosen):\n",
    "        ele = heapq.heappop(chosen)\n",
    "        heapq.heappush(dest, ele)\n",
    "class Solution:\n",
    "    \n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        import string\n",
    "        dict = {c : 0 for c in string.ascii_lowercase}\n",
    "        for char in s:\n",
    "            dict[char] = dict[char] + 1\n",
    "        candidates = [heap_item(x[0], x[1]) for x in dict.items() if x[1] != 0]\n",
    "        chosen = []\n",
    "        import heapq \n",
    "        heapq.heapify(candidates)\n",
    "        heapq.heapify(chosen)\n",
    "        res = \"\"\n",
    "        while len(candidates):\n",
    "            # print(candidates)\n",
    "            c_insert = heapq.heappop(candidates)\n",
    "            # print(c_insert)\n",
    "            pos = res.rfind(c_insert.key)\n",
    "            while pos != -1 and len(res) - pos < k:\n",
    "                heapq.heappush(chosen, c_insert)\n",
    "                if len(candidates) == 0:\n",
    "                    return \"\"\n",
    "                c_insert = heapq.heappop(candidates)\n",
    "                pos = res.rfind(c_insert.key)\n",
    "            res = res + c_insert.key\n",
    "            # print(f\"new str is {res}\")\n",
    "            c_insert.value = c_insert.value - 1\n",
    "            if c_insert.value:\n",
    "                heapq.heappush(chosen, c_insert)\n",
    "            put_chosen(candidates, chosen)     \n",
    "            assert len(chosen) == 0, \"bad bad qwq\"\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        from collections import Counter\n",
    "        import heapq\n",
    "        if k <= 1: return s\n",
    "        c = Counter(s)\n",
    "        n = len(s)\n",
    "        heap = [(-v, k) for k, v in c.items()]\n",
    "        heapq.heapify(heap)\n",
    "        res = \"\"\n",
    "        while heap:\n",
    "            tmp = []\n",
    "            for _ in range(k):\n",
    "                if not heap:return res if len(res) == n else \"\"\n",
    "                num, alp = heapq.heappop(heap)\n",
    "                num += 1\n",
    "                res += alp\n",
    "                if num != 0:\n",
    "                    tmp.append((num, alp))\n",
    "            for t in tmp:\n",
    "                heapq.heappush(heap, t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        counter = collections.Counter(s)\n",
    "        h = []\n",
    "        for s, c in counter.items():\n",
    "            heapq.heappush(h, (-c, s))\n",
    "\n",
    "        ret = \"\"\n",
    "        while h:\n",
    "            tmp = [heapq.heappop(h) for _ in range(min(k, len(h)))]\n",
    "            if len(tmp) < k:\n",
    "                for neg_c, s in tmp:\n",
    "                    if neg_c < -1:\n",
    "                        return \"\"\n",
    "            for neg_c, s in tmp:\n",
    "                ret += s\n",
    "                if neg_c != -1:\n",
    "                    heapq.heappush(h, (neg_c + 1, s))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        from heapq import heappush, heappop\n",
    "        from collections import defaultdict\n",
    "        if k == 0:\n",
    "            return s\n",
    "        res = \"\"\n",
    "        myPool = []\n",
    "        myPQ = []\n",
    "        myDict = defaultdict(int)\n",
    "        for ss in s:\n",
    "            myDict[ss] += 1\n",
    "        for key, value in myDict.items():\n",
    "            heappush(myPQ, (-value, key))\n",
    "        \n",
    "        TotalLen = len(s)\n",
    "        for i in range(TotalLen):\n",
    "            # print(res, myPool, myPQ)\n",
    "            idx = 0\n",
    "            while idx < len(myPool):\n",
    "                key, times, wl = myPool[idx]\n",
    "                wl -= 1\n",
    "                if wl == 0:\n",
    "                    myPool.pop(idx)\n",
    "                    heappush(myPQ, (-times, key))\n",
    "                else:\n",
    "                    myPool[idx] = (key, times, wl)\n",
    "                    idx += 1\n",
    "            if not myPQ:\n",
    "                return \"\"\n",
    "            times, key = heappop(myPQ)\n",
    "            times *= -1\n",
    "            res += key\n",
    "            times -= 1\n",
    "            if times > 0:\n",
    "                myPool.append((key,times, k))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        record = collections.defaultdict(int)\n",
    "        for c in s:\n",
    "            record[c] += 1\n",
    "        dp = [[-1*record[c], c] for c in record]\n",
    "        heapq.heapify(dp)\n",
    "\n",
    "        queue = []\n",
    "        res = ''\n",
    "\n",
    "        while dp:\n",
    "            num, char = heapq.heappop(dp)\n",
    "            freq = -1*num\n",
    "            res += char\n",
    "            queue.append([freq-1, char])\n",
    "            if len(queue) == k:\n",
    "                freq, char = queue.pop(0)\n",
    "                if freq > 0:\n",
    "                    heapq.heappush(dp, [-1*freq, char])\n",
    "        return res if len(res) == len(s) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        from collections import defaultdict\n",
    "        from heapq import heapify, heappop, heappush\n",
    "\n",
    "        if k == 0:\n",
    "            return s\n",
    "\n",
    "        char_counts = defaultdict(int)\n",
    "        for c in s:\n",
    "            char_counts[c] -= 1\n",
    "        \n",
    "        char_heap = []\n",
    "        for c in char_counts.keys():\n",
    "            c_tuple = (char_counts[c], c)\n",
    "            heappush(char_heap, c_tuple)\n",
    "        \n",
    "        # print(char_heap)\n",
    "        res = \"\"\n",
    "        temp = []\n",
    "        cur_char_set = set()\n",
    "        while char_heap:\n",
    "\n",
    "            cur_k = k\n",
    "            cur_char_set.clear()\n",
    "            while cur_k > 0:\n",
    "                if char_heap:\n",
    "                    cur_count, cur_char = heappop(char_heap)\n",
    "                    \n",
    "                    res += cur_char\n",
    "                    cur_count += 1\n",
    "                    cur_char_set.add(cur_char)\n",
    "\n",
    "                    if cur_count != 0:\n",
    "                        temp.append((cur_count, cur_char))\n",
    "                else: \n",
    "                    break\n",
    "                \n",
    "                cur_k -= 1\n",
    "            \n",
    "            # print(\"-------------\")\n",
    "            # print(temp)\n",
    "            # print(cur_k)\n",
    "            if len(temp) < k and cur_k > 0:\n",
    "                for count, c in temp:\n",
    "                    if c in cur_char_set:\n",
    "                        return \"\"\n",
    "            \n",
    "            while temp:\n",
    "                heappush(char_heap, temp.pop())\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        from collections import defaultdict\n",
    "        mem = defaultdict(int)\n",
    "        for _ in s:\n",
    "            mem[_] += 1\n",
    "        qq = []\n",
    "        for _, v in mem.items():\n",
    "            qq.append([-1, v, _])\n",
    "        cur = 0\n",
    "        tmp = []\n",
    "        ans = \"\"\n",
    "        while qq or tmp:\n",
    "            while qq:\n",
    "                if cur - qq[0][0] >= k or qq[0][0] == -1:\n",
    "                    tmp.append(qq.pop(0))\n",
    "                else:\n",
    "                    break\n",
    "            if len(tmp) == 0:\n",
    "                return \"\"\n",
    "            tmp = sorted(tmp, key=lambda x: x[1], reverse=True)\n",
    "            tmp[0] = [cur, tmp[0][1] - 1, tmp[0][2]]\n",
    "            ans += tmp[0][2]\n",
    "            cur += 1\n",
    "            if tmp[0][1] != 0:\n",
    "                qq += [tmp[0]]\n",
    "            tmp.pop(0)\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        counter = Counter(s)\n",
    "        pq = [[-v, c] for c, v in counter.items()]  # -freq, char\n",
    "        heapq.heapify(pq)\n",
    "        last_pos = defaultdict(lambda: float('-inf'))  # char: last position\n",
    "        res = ''\n",
    "        while pq:\n",
    "            tmp = []\n",
    "            while pq and len(res) - last_pos[pq[0][1]] < k:\n",
    "                freq, char = heapq.heappop(pq)\n",
    "                tmp.append([freq, char])\n",
    "            if not pq:\n",
    "                return ''\n",
    "            freq, char = heapq.heappop(pq)\n",
    "            res += char\n",
    "            last_pos[char] = len(res) - 1  # update last position\n",
    "            if freq + 1:\n",
    "                tmp.append([freq + 1, char])\n",
    "            for freq, char in tmp:\n",
    "                heapq.heappush(pq, [freq, char])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        counter = collections.Counter(s)\n",
    "        h = []\n",
    "        for s, c in counter.items():\n",
    "            heapq.heappush(h, (-c, s))\n",
    "\n",
    "        ret = \"\"\n",
    "        while h:\n",
    "            tmp = [heapq.heappop(h) for _ in range(min(k, len(h)))]\n",
    "            for neg_c, s in tmp:\n",
    "                if len(tmp) < k and neg_c < -1:\n",
    "                    return \"\"\n",
    "                ret += s\n",
    "                if neg_c != -1:\n",
    "                    heapq.heappush(h, (neg_c + 1, s))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        s_fre = collections.defaultdict(int)\n",
    "        for c in s:\n",
    "            s_fre[c] += 1\n",
    "        \n",
    "        heap = []\n",
    "        for c in s_fre:\n",
    "            heapq.heappush(heap, (-s_fre[c], c))\n",
    "        \n",
    "        output = \"\"\n",
    "        queue = collections.deque()\n",
    "\n",
    "        while heap:\n",
    "            fre, c = heapq.heappop(heap)\n",
    "            fre = - fre\n",
    "            output += c\n",
    "            fre -= 1\n",
    "            queue.append((fre, c))\n",
    "\n",
    "            if len(queue) == k:\n",
    "                f, c = queue.popleft()\n",
    "                if f > 0:\n",
    "                    heapq.heappush(heap, (-f, c))\n",
    "        return output if len(output) == len(s) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        import heapq\n",
    "\n",
    "        # k距离间隔字符串重排\n",
    "        # 每一次确定输出字符都要份两步，一是确定那些字符可以用，二是确定应该用哪个字符，即哪个字符剩余最多；\n",
    "        from collections import defaultdict\n",
    "        mem = defaultdict(int)\n",
    "        for _ in s:\n",
    "            mem[_] += 1\n",
    "        mh = []\n",
    "        for _, v in mem.items():\n",
    "            heapq.heappush(mh, [-v, _])\n",
    "        qq = []\n",
    "        ans = \"\"\n",
    "        while mh:\n",
    "            cnt, char = heapq.heappop(mh)\n",
    "            ans += char\n",
    "            qq.append([cnt + 1, char])\n",
    "            if len(qq) >= k:\n",
    "                rec_v, rec_k = qq.pop(0)\n",
    "                if rec_v != 0:\n",
    "                    heapq.heappush(mh, [rec_v, rec_k])\n",
    "        print(ans)\n",
    "        if len(qq) != 0:\n",
    "            while qq:\n",
    "                cnt, _ = qq.pop()\n",
    "                if cnt != 0:\n",
    "                    return \"\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        wordcount, h, q = {}, [], collections.deque()\n",
    "        ans = ''\n",
    "\n",
    "        for c in s:\n",
    "            if c not in wordcount:\n",
    "                wordcount[c] = 1\n",
    "            else:\n",
    "                wordcount[c] += 1\n",
    "        \n",
    "        for c, count in wordcount.items():\n",
    "            heapq.heappush(h, (-count, c))\n",
    "        \n",
    "        while h:\n",
    "            count, c = heapq.heappop(h)\n",
    "            ans += c\n",
    "            q.append((count + 1, c))\n",
    "            if len(q) >= k:\n",
    "                ncount, nc = q.popleft()\n",
    "                if ncount != 0:\n",
    "                    heapq.heappush(h, (ncount, nc))\n",
    "\n",
    "        return ans if len(s) == len(ans) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        \n",
    "        chr_freq = collections.Counter(s)\n",
    "        \n",
    "        maxHeap = [(-1 * freq, chr) for chr, freq in chr_freq.items()]\n",
    "        heapq.heapify(maxHeap)\n",
    "        \n",
    "        Q = collections.deque()\n",
    "        res = \"\"\n",
    "        while maxHeap:\n",
    "            freq, c = heapq.heappop(maxHeap)    #要想实现，必须先弹出最大次数的那个\n",
    "            freq *= -1\n",
    "\n",
    "            res += c\n",
    "            Q.append((freq - 1, c))\n",
    "\n",
    "            if len(Q) == k:             #能够构成一个长度为k的窗口。则后移\n",
    "                f, c = Q.popleft()\n",
    "                if f > 0:\n",
    "                    heapq.heappush(maxHeap, (-1 * f, c))\n",
    "        \n",
    "        return res if len(res) == len(s) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        count = Counter(s)\n",
    "        count = sorted([[key, value] for key, value in count.items()], key=lambda x:x[1], reverse=True)\n",
    "        if k == 0 or count[0][1] == 1:\n",
    "            return s\n",
    "        res = \"\"\n",
    "        while count:\n",
    "            i = 0\n",
    "            for _ in range(k):\n",
    "                if i >= len(count):\n",
    "                    return \"\"\n",
    "                res += count[i][0]\n",
    "                count[i][1] -= 1\n",
    "                if count[i][1] == 0:\n",
    "                    count.pop(i)\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "                if len(res) == len(s):\n",
    "                    return res\n",
    "            count = sorted(count,key=lambda x:x[1], reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        \n",
    "        chr_freq = collections.Counter(s)\n",
    "        \n",
    "        maxHeap = [(-1 * freq, chr) for chr, freq in chr_freq.items()]\n",
    "        heapq.heapify(maxHeap)\n",
    "        \n",
    "        Q = collections.deque()\n",
    "        res = \"\"\n",
    "        while maxHeap:\n",
    "            freq, c = heapq.heappop(maxHeap)    #要想实现，必须先弹出最大次数的那个\n",
    "            freq *= -1\n",
    "\n",
    "            res += c\n",
    "            Q.append((freq - 1, c))\n",
    "\n",
    "            if len(Q) == k:             #能够构成一个长度为k的窗口。则后移\n",
    "                f, c = Q.popleft()\n",
    "                if f > 0:\n",
    "                    heapq.heappush(maxHeap, (-1 * f, c))\n",
    "        \n",
    "        return res if len(res) == len(s) else \"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1:\n",
    "            return s\n",
    "        \n",
    "        chr_freq = collections.Counter(s)\n",
    "        \n",
    "        maxHeap = [(-1 * freq, chr) for chr, freq in chr_freq.items()]\n",
    "        heapq.heapify(maxHeap)\n",
    "\n",
    "        Q = collections.deque()\n",
    "        res = \"\"\n",
    "        while maxHeap:\n",
    "            freq, c = heapq.heappop(maxHeap)    #要想实现，必须先弹出最大次数的那个\n",
    "            freq *= -1\n",
    "\n",
    "            res += c\n",
    "            Q.append((freq - 1, c))\n",
    "\n",
    "            if len(Q) == k:             #能够构成一个长度为k的窗口。则后移\n",
    "                f, c = Q.popleft()\n",
    "                if f > 0:\n",
    "                    heapq.heappush(maxHeap, (-1 * f, c))\n",
    "        \n",
    "        return res if len(res) == len(s) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1:\n",
    "            return s\n",
    "        \n",
    "        chr_freq = collections.Counter(s)\n",
    "        \n",
    "        maxHeap = [(-1 * freq, chr) for chr, freq in chr_freq.items()]\n",
    "        heapq.heapify(maxHeap)\n",
    "\n",
    "        Q = collections.deque()\n",
    "        res = \"\"\n",
    "        while maxHeap:\n",
    "            freq, c = heapq.heappop(maxHeap)    #要想实现，必须先弹出最大次数的那个\n",
    "            freq *= -1\n",
    "\n",
    "            res += c\n",
    "            Q.append((freq - 1, c))\n",
    "\n",
    "            if len(Q) == k:             #能够构成一个长度为k的窗口。则后移\n",
    "                f, c = Q.popleft()\n",
    "                if f > 0:\n",
    "                    heapq.heappush(maxHeap, (-1 * f, c))\n",
    "        \n",
    "        return res if len(res) == len(s) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        counter = collections.Counter(s)\n",
    "        dq = collections.deque()\n",
    "        heap = []\n",
    "        for c in counter:\n",
    "            heapq.heappush(heap, [- counter[c], c])\n",
    "        res = ''\n",
    "        while heap:\n",
    "            # print(res)\n",
    "            _, c = heapq.heappop(heap)\n",
    "            res += c  \n",
    "            counter[c] -= 1 \n",
    "            dq.append(c)\n",
    "            if len(dq) > 0 and len(dq) >= k:\n",
    "                new = dq.popleft()\n",
    "                if counter[new] > 0:\n",
    "                    heapq.heappush(heap, [- counter[new], new])\n",
    "        return res if len(res) == len(s) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        d = Counter(s) \n",
    "        numlist = [(-num,s) for s, num in d.items()]\n",
    "        heapify(numlist)\n",
    "        numappear = collections.deque([(0,0) for _ in range(k-1)])\n",
    "        snumapp = 0\n",
    "        ans = ''\n",
    "        if len(numlist)<k:\n",
    "            return ''\n",
    "        while numlist:\n",
    "            topnum, tops = heapq.heappop(numlist)\n",
    "            topnum = -topnum\n",
    "            ans+=tops\n",
    "            if topnum>0:\n",
    "                numappear.append((-(topnum-1),tops))\n",
    "                snumapp+= topnum-1\n",
    "            else:\n",
    "                numappear.append((0,0))\n",
    "            tnum, ts = numappear.popleft()\n",
    "            if tnum != 0:\n",
    "                heapq.heappush(numlist, (tnum, ts))\n",
    "                snumapp-=-tnum\n",
    "        return ans if len(ans)==len(s) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        maps = dict()\n",
    "        for c in s:\n",
    "            maps[c] = maps.get(c, 0) + 1\n",
    "        heap_assist = []\n",
    "        for c in maps:\n",
    "            heappush(heap_assist, (-maps[c], c))\n",
    "        s_out = ''\n",
    "        ready = collections.deque()\n",
    "        while heap_assist:\n",
    "            _, c = heappop(heap_assist)\n",
    "            s_out += c\n",
    "            maps[c] -= 1\n",
    "            ready.append(c)\n",
    "            if len(ready)>=k:\n",
    "                a = ready.popleft()\n",
    "                if maps[a]:\n",
    "                    heappush(heap_assist, (-maps[a], a))\n",
    "        if len(s_out) == len(s):\n",
    "            return s_out\n",
    "        else:\n",
    "            return ''\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        d = Counter(s) \n",
    "        numlist = [(-num,s) for s, num in d.items()]\n",
    "        heapify(numlist)\n",
    "        numappear = collections.deque([(0,0) for _ in range(k-1)])\n",
    "        snumapp = 0\n",
    "        ans = ''\n",
    "        if len(numlist)<k:\n",
    "            return ''\n",
    "        while numlist:\n",
    "            topnum, tops = heapq.heappop(numlist)\n",
    "            topnum = -topnum\n",
    "            ans+=tops\n",
    "            if topnum>0:\n",
    "                numappear.append((-(topnum-1),tops))\n",
    "                snumapp+= topnum-1\n",
    "            else:\n",
    "                numappear.append((0,0))\n",
    "            tnum, ts = numappear.popleft()\n",
    "            if tnum != 0:\n",
    "                heapq.heappush(numlist, (tnum, ts))\n",
    "                snumapp-=-tnum\n",
    "        return ans if len(ans)==len(s) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        \n",
    "        chr_freq = collections.Counter(s)\n",
    "        \n",
    "        maxHeap = [(-1 * freq, chr) for chr, freq in chr_freq.items()]\n",
    "        heapq.heapify(maxHeap)\n",
    "        \n",
    "        Q = collections.deque()\n",
    "        res = \"\"\n",
    "        while maxHeap:\n",
    "            freq, c = heapq.heappop(maxHeap)    #要想实现，必须先弹出最大次数的那个\n",
    "            freq *= -1\n",
    "\n",
    "            res += c\n",
    "            Q.append((freq - 1, c))\n",
    "\n",
    "            if len(Q) == k:             #能够构成一个长度为k的窗口。则后移\n",
    "                f, c = Q.popleft()\n",
    "                if f > 0:\n",
    "                    heapq.heappush(maxHeap, (-1 * f, c))\n",
    "        \n",
    "        return res if len(res) == len(s) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, p: int) -> str:\n",
    "        cnt = Counter(s)\n",
    "        pq = []\n",
    "        mx = 0\n",
    "        \n",
    "        for k, v in cnt.items():\n",
    "            pq.append((k, v))\n",
    "            mx = max(mx, v)\n",
    "        pq.sort(key = lambda x : -x[1])\n",
    "        arr = [''] * mx\n",
    "        \n",
    "        idx = 0\n",
    "        for k, v in pq:\n",
    "            for i in range(v):\n",
    "                if idx == mx - 1 and v < mx:\n",
    "                    idx = 0\n",
    "                arr[idx] += k\n",
    "                idx += 1\n",
    "                idx %= mx\n",
    "        for i in range(mx - 1):\n",
    "            if len(arr[i]) < p:\n",
    "                return ''\n",
    "        return ''.join(arr)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int):\n",
    "        n = len(s)\n",
    "        idx = 0\n",
    "        words = collections.Counter(s)\n",
    "        new_items = [(k, v) for k, v in words.items()]\n",
    "        new_items = sorted(new_items, key=lambda x: x[1], reverse=True)\n",
    "        mx = max(item[1] for item in new_items)\n",
    "        new_word = [\"\"] * mx\n",
    "        for key, v in new_items:\n",
    "            for i in range(v):\n",
    "                if v < mx and idx == mx - 1:\n",
    "                    idx = 0\n",
    "                new_word[idx] += key\n",
    "                idx += 1\n",
    "                idx %= mx\n",
    "\n",
    "        for i in range(mx - 1):\n",
    "            if len(new_word[i]) < k:\n",
    "                return \"\"\n",
    "        return \"\".join(new_word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        word_dict = collections.Counter(s)\n",
    "        word_list = [(key, v) for key, v in word_dict.items()]\n",
    "        s_list = sorted(word_list, key=lambda x: x[1], reverse=True)\n",
    "        mx = s_list[0][1]\n",
    "        ans_list = [\"\"] * mx\n",
    "        idx = 0\n",
    "\n",
    "        for key, v in s_list:\n",
    "            for i in range(v):\n",
    "                if v < mx and idx == mx-1:\n",
    "                    idx = 0\n",
    "                ans_list[idx] += key\n",
    "                idx += 1\n",
    "                idx %= mx\n",
    "\n",
    "        for item in ans_list[:-1]:\n",
    "            if len(item) < k:\n",
    "                return \"\"\n",
    "        ans = \"\".join(ans_list)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1:\n",
    "            return s\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        dic = sorted([(t, c) for c, t in Counter(s).items()])\n",
    "        for i in range(0, len(s), k):\n",
    "            pos = min(k, len(s) - i)\n",
    "            if pos > len(dic):\n",
    "                return \"\"\n",
    "            ans += [dic[-j][1] for j in range(1, pos + 1)]\n",
    "            dic = list(merge(dic[:len(dic) - pos], [(t - 1, c) for t, c in dic[len(dic) - pos:] if t - 1]))\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        counter = collections.Counter(s)\n",
    "        h = []\n",
    "        for s, c in counter.items():\n",
    "            heapq.heappush(h, (-c, s))\n",
    "\n",
    "        ret = []\n",
    "        while h:\n",
    "            tmp = [heapq.heappop(h) for _ in range(min(k, len(h)))]\n",
    "            for neg_c, s in tmp:\n",
    "                if len(tmp) < k and neg_c < -1:\n",
    "                    return \"\"\n",
    "                ret.append(s)\n",
    "                if neg_c != -1:\n",
    "                    heapq.heappush(h, (neg_c + 1, s))\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1 : return s\n",
    "        res, n = [] , len(s) \n",
    "        c = sorted([(b,a) for a,b in Counter(s).items()])\n",
    "        for i in range(0,n,k):\n",
    "            K = min(k , n - i)\n",
    "            if len(c) < K : return \"\"\n",
    "            res += [c[-j][1] for j in range(1,K+1)]\n",
    "            c = list(merge(c[:len(c)-K],[(cnt-1,ch) for cnt,ch in c[len(c)-K:] if cnt-1]))\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1: return s \n",
    "        res, n = [], len(s)\n",
    "        c = sorted([(b, a) for a, b in Counter(s).items()])\n",
    "        for i in range(0, n, k):\n",
    "            K = min(k, n - i)\n",
    "            if len(c) < K: return \"\"\n",
    "            res += [c[-j][1] for j in range(1, K+1)]\n",
    "            c = list(merge(c[:len(c) - K], [(cnt-1, ch) for cnt, ch in c[len(c)-K:] if cnt-1]))\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k < 2:\n",
    "            return s\n",
    "        cnt = Counter(s)\n",
    "        n = len(s)\n",
    "        heap = [(-v, k) for k, v in cnt.items()]\n",
    "        heapify(heap)\n",
    "        res = []\n",
    "        while heap:\n",
    "            tmp = []\n",
    "            for _ in range(k):\n",
    "                if not heap:\n",
    "                    return ''.join(res) if len(res) == n else ''\n",
    "                num, key = heappop(heap)\n",
    "                num += 1\n",
    "                res.append(key)\n",
    "                if num != 0:\n",
    "                    tmp.append((num, key))\n",
    "            for t in tmp:\n",
    "                heappush(heap, t)\n",
    "        return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1 : return s\n",
    "        res, n = [] , len(s) \n",
    "        c = sorted([(b,a) for a,b in Counter(s).items()])\n",
    "        for i in range(0,n,k):\n",
    "            K = min(k , n - i)\n",
    "            if len(c) < K : return \"\"\n",
    "            res += [c[-j][1] for j in range(1,K+1)]\n",
    "            c = list(merge(c[:len(c)-K],[(cnt-1,ch) for cnt,ch in c[len(c)-K:] if cnt-1]))\n",
    "        return \"\".join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1 : return s\n",
    "        res, n = [] , len(s) \n",
    "        c = sorted([(b,a) for a,b in Counter(s).items()])\n",
    "        for i in range(0,n,k):\n",
    "            K = min(k , n - i)\n",
    "            if len(c) < K : return \"\"\n",
    "            res += [c[-j][1] for j in range(1,K+1)]\n",
    "            c = list(merge(c[:len(c)-K],[(cnt-1,ch) for cnt,ch in c[len(c)-K:] if cnt-1]))\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k <= 1:\n",
    "            return s\n",
    "        # 通过加入负数方式实现大顶堆\n",
    "        dic = {}\n",
    "        for c in s:\n",
    "            if c in dic:\n",
    "                dic[c] -= 1\n",
    "            else:\n",
    "                dic[c] = -1\n",
    "        if len(dic) < k:\n",
    "            return \"\"\n",
    "\n",
    "        # 定义结果字符数组、字符队列（存放暂时不能用的字符）、堆（所有可用字符，捡着最多的用）\n",
    "        result = []\n",
    "        q = deque()\n",
    "        heap = []\n",
    "        for d in dic.items():\n",
    "            heap.append([d[1], d[0]])\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        while heap:\n",
    "            # 从堆（可用字符）中选出个数最多的加入结果数组中，并将其扔进（暂不可用）队列\n",
    "            ch = heapq.heappop(heap)\n",
    "            result.append(ch[1])\n",
    "            ch[0] += 1\n",
    "            q.appendleft(ch)\n",
    "            # 若队列够k个则滚出一个，个数不为0继续扔进（可用）堆中\n",
    "            # 由于捡着多的用（消耗个数多的），队列中字符的个数逐步变小，最终全部向0看齐\n",
    "            if len(q) == k:\n",
    "                item = q.pop()\n",
    "                if item[0] < 0:\n",
    "                    heapq.heappush(heap, item)\n",
    "        \n",
    "        if len(result) < len(s):\n",
    "            return \"\"\n",
    "        return \"\".join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k==0:\n",
    "            return s\n",
    "        counter = Counter(s)\n",
    "        N = len(s)\n",
    "        candidates = [(counter[c],c) for c in counter]\n",
    "        candidates.sort(reverse=True)\n",
    "        maxCnt = candidates[0][0]\n",
    "        maxCntNum = 0 \n",
    "        for i in range(len(candidates)):\n",
    "            if candidates[i][0]==maxCnt:\n",
    "                maxCntNum+=1\n",
    "            else:\n",
    "                break \n",
    "        nK,nleft = N//k,N%k\n",
    "        # print(counter)\n",
    "        if maxCnt>nK and not (maxCnt==nK+1 and maxCntNum<=nleft):\n",
    "            return \"\"\n",
    "        ret = [\"\"]*N\n",
    "        i,j = 0,0\n",
    "        for cnt,c in candidates:\n",
    "            for _ in range(cnt):\n",
    "                ret[i*k+j] = c \n",
    "                i+=1 \n",
    "                if i*k+j>=N:\n",
    "                    i=0 \n",
    "                    j+=1\n",
    "            # print(ret)\n",
    "\n",
    "        for i in range(N):\n",
    "            if i+k<N and  ret[i]==ret[i+k-1]:\n",
    "                ret[i+k-1],ret[i+k] = ret[i+k],ret[i+k-1]\n",
    "\n",
    "\n",
    "        return \"\".join(ret) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, K: int) -> str:\n",
    "        if K == 0: return s\n",
    "\n",
    "        limit = [0] * 26\n",
    "        class Item:\n",
    "            def __init__(self, idx, times):\n",
    "                self.idx = idx\n",
    "                self.times = times\n",
    "\n",
    "            def __lt__(self, other) -> bool:\n",
    "                if limit[self.idx] == limit[other.idx] == 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] != 0 and limit[other.idx] != 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] == 0:\n",
    "                    return True\n",
    "                if limit[other.idx] == 0:\n",
    "                    return False\n",
    "            \n",
    "        count = []\n",
    "        for k, v in Counter(s).items():\n",
    "            count.append(Item(ord(k)-ord('a'), v))\n",
    "        result = []\n",
    "        while count:\n",
    "            heapq.heapify(count)\n",
    "            item = heapq.heappop(count)\n",
    "            if limit[item.idx] != 0:\n",
    "                return \"\"\n",
    "            result.append(chr(ord('a')+item.idx))\n",
    "            for other in count:\n",
    "                if limit[other.idx] != 0:\n",
    "                    limit[other.idx] -= 1\n",
    "            item.times-=1\n",
    "            if item.times != 0:\n",
    "                limit[item.idx] = K - 1\n",
    "                heapq.heappush(count, item)\n",
    "        return \"\".join(result)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my：双指针+哈希 51/64--pass\n",
    "# ### \"aabbcc\"，k==2 error\n",
    "# from collections import Counter\n",
    "# class Solution:\n",
    "#     def rearrangeString(self, s: str, k: int) -> str:\n",
    "#         if k==0:return s\n",
    "#         cnt=Counter(s)\n",
    "#         n=len(s)\n",
    "#         for v in cnt.values():\n",
    "#             if (n+1)//v<k:return \"\" \n",
    "#         res=[\"\"]*n\n",
    "#         cnt=sorted(cnt.items(),key=lambda v:(-v[1]))\n",
    "#         i=0\n",
    "#         for kk,v in cnt:\n",
    "#             while i<n and res[i]!=\"\":\n",
    "#                 i+=1\n",
    "#             j=i\n",
    "#             cnt=0\n",
    "#             while j<n and cnt<v:\n",
    "#                 res[j]=kk \n",
    "#                 j+=k #if k>0 else j+1\n",
    "#                 cnt+=1\n",
    "#         return \"\".join(res)\n",
    "\n",
    "\n",
    "### my：哈希+数组（refer 网友） \n",
    "### \"aabbcc\"，k==2 error\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k==0:return s\n",
    "        cnt=Counter(s)\n",
    "        n=len(s)\n",
    "        # for v in cnt.values(): ### \"abeabac\" k==3 error\n",
    "        #     if (n+1)//v<k:return \"\" \n",
    "        res=[\"\"]*n\n",
    "        cnt=sorted(cnt.items(),key=lambda v:(-v[1]))\n",
    "        m=cnt[0][1]\n",
    "        \n",
    "        res=[[] for _ in range(m)]\n",
    "        j=0\n",
    "        for kk,v in cnt:\n",
    "            if v==m:\n",
    "                for i in range(v):\n",
    "                    res[i].append(kk)\n",
    "            else:\n",
    "                for _ in range(v):\n",
    "                    res[j].append(kk)\n",
    "                    j=(j+1)%(m-1)\n",
    "\n",
    "        for i in range(m-1): ### 除最后一组的前m-1组，长度都得>=k\n",
    "            if len(res[i])<k:\n",
    "                return \"\"\n",
    "\n",
    "        return \"\".join([\"\".join(res[i]) for i in range(m)])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        n = len(s)\n",
    "        if k == 0: return s\n",
    "        # cap = math.ceil(7/k)\n",
    "        #a count arr map? \n",
    "        cnt = [0 for _ in range(26)]\n",
    "        # cntAscI = [i for i in range(26)]\n",
    "        for c in s:\n",
    "            i = ord(c)-ord('a')\n",
    "            cnt[i]+=1\n",
    "        maxHeap = []\n",
    "        for i in range(26):\n",
    "            if cnt[i] != 0:\n",
    "                heapq.heappush(maxHeap, (-cnt[i], i))\n",
    "        pq = collections.deque()\n",
    "        ret = []\n",
    "        while maxHeap:\n",
    "            cntI, i = heapq.heappop(maxHeap)\n",
    "            # print(i)\n",
    "            ret.append(chr(ord('a')+i))\n",
    "            pq.append((cntI+1, i))\n",
    "            if len(pq) == k:\n",
    "                newItem = pq.popleft()\n",
    "                if newItem[0] != 0:\n",
    "                    heapq.heappush(maxHeap, newItem)\n",
    "        print(ret)\n",
    "        if len(ret) != n: return \"\"\n",
    "        return \"\".join(ret)\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, K: int) -> str:\n",
    "        if K == 0: return s\n",
    "        limit = [0] * 26\n",
    "        class Item:\n",
    "            def __init__(self, idx, times):\n",
    "                self.idx = idx\n",
    "                self.times = times\n",
    "\n",
    "            def __lt__(self, other) -> bool:\n",
    "                if limit[self.idx] == limit[other.idx] == 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] != 0 and limit[other.idx] != 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] == 0:\n",
    "                    return True\n",
    "                if limit[other.idx] == 0:\n",
    "                    return False\n",
    "            \n",
    "            # def __repr__(self):\n",
    "            #     return f\"{chr(97+self.idx)},Times: {self.times},Limit: {limit[self.idx]}\\n\"\n",
    "        count = []\n",
    "        for k, v in Counter(s).items():\n",
    "            count.append(Item(ord(k)-ord('a'), v))\n",
    "        heapq.heapify(count)\n",
    "        result = []\n",
    "        while count:\n",
    "            item = heapq.heappop(count)\n",
    "            if limit[item.idx] != 0:\n",
    "                return \"\"\n",
    "            result.append(chr(ord('a')+item.idx))\n",
    "            for other in count:\n",
    "                if limit[other.idx] != 0:\n",
    "                    limit[other.idx] -= 1\n",
    "            item.times-=1\n",
    "            if item.times != 0:\n",
    "                limit[item.idx] = K - 1\n",
    "                heapq.heappush(count, item)\n",
    "            heapq.heapify(count)\n",
    "        print(result)\n",
    "        return \"\".join(result)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, K: int) -> str:\n",
    "        if K == 0: return s\n",
    "        limit = [0] * 26\n",
    "        class Item:\n",
    "            def __init__(self, idx, times):\n",
    "                self.idx = idx\n",
    "                self.times = times\n",
    "\n",
    "            def __lt__(self, other) -> bool:\n",
    "                if limit[self.idx] == limit[other.idx] == 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] != 0 and limit[other.idx] != 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] == 0:\n",
    "                    return True\n",
    "                if limit[other.idx] == 0:\n",
    "                    return False\n",
    "            \n",
    "        count = []\n",
    "        for k, v in Counter(s).items():\n",
    "            count.append(Item(ord(k)-ord('a'), v))\n",
    "        result = []\n",
    "        while count:\n",
    "            heapq.heapify(count)\n",
    "            item = heapq.heappop(count)\n",
    "            if limit[item.idx] != 0:\n",
    "                return \"\"\n",
    "            result.append(chr(ord('a')+item.idx))\n",
    "            for other in count:\n",
    "                if limit[other.idx] != 0:\n",
    "                    limit[other.idx] -= 1\n",
    "            item.times-=1\n",
    "            if item.times != 0:\n",
    "                limit[item.idx] = K - 1\n",
    "                heapq.heappush(count, item)\n",
    "        print(result)\n",
    "        return \"\".join(result)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, K: int) -> str:\n",
    "        if K == 0: return s\n",
    "        limit = [0] * 26\n",
    "        class Item:\n",
    "            def __init__(self, idx, times):\n",
    "                self.idx = idx\n",
    "                self.times = times\n",
    "\n",
    "            def increase(self):\n",
    "                self.times+=1\n",
    "            \n",
    "            def decrease(self):\n",
    "                self.times-=1\n",
    "\n",
    "            def __lt__(self, other) -> bool:\n",
    "                if limit[self.idx] == limit[other.idx] == 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] != 0 and limit[other.idx] != 0:\n",
    "                    return self.times > other.times\n",
    "                if limit[self.idx] == 0:\n",
    "                    return True\n",
    "                if limit[other.idx] == 0:\n",
    "                    return False\n",
    "            \n",
    "            def __repr__(self):\n",
    "                return f\"{chr(97+self.idx)},Times: {self.times},Limit: {limit[self.idx]}\\n\"\n",
    "        count = []\n",
    "        for k, v in Counter(s).items():\n",
    "            count.append(Item(ord(k)-ord('a'), v))\n",
    "        heapq.heapify(count)\n",
    "        result = []\n",
    "        while count:\n",
    "            item = heapq.heappop(count)\n",
    "            if limit[item.idx] != 0:\n",
    "                return \"\"\n",
    "            result.append(chr(ord('a')+item.idx))\n",
    "            for other in count:\n",
    "                if limit[other.idx] != 0:\n",
    "                    limit[other.idx] -= 1\n",
    "            item.decrease()\n",
    "            if item.times != 0:\n",
    "                limit[item.idx] = K - 1\n",
    "                heapq.heappush(count, item)\n",
    "            heapq.heapify(count)\n",
    "        print(result)\n",
    "        return \"\".join(result)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeString(self, s: str, k: int) -> str:\n",
    "        if k == 0:\n",
    "            return s\n",
    "        cnt_li = [(-v, k) for k, v in Counter(s).items()]\n",
    "        heapq.heapify(cnt_li)\n",
    "        res = []\n",
    "        q = deque([])\n",
    "        while cnt_li:\n",
    "            pair = heapq.heappop(cnt_li)\n",
    "            res.append(pair[1])\n",
    "            q.append((pair[0] + 1, pair[1]))\n",
    "            if len(q) == k:\n",
    "                pair = q.popleft()\n",
    "                if pair[0] < 0:\n",
    "                    heapq.heappush(cnt_li, pair) \n",
    "        return res if len(res) == len(s) else \"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
